package com.algorithm.排序.基于比较的排序;

import com.algorithm.排序.Sort;

//@SuppressWarnings("all")
public class 快速排序 <E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        sort(0,array.length);
    }

    /**
     * 对[begin,end)  范围的元素进行排序
     * @param begin
     * @param end
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) return;

        // 确定轴点位置
        int mid = pivotIndex(begin, end);

        // 对轴点左右的子序列进行快速排序
        sort(begin,mid);
        sort(mid + 1,end);
    }

    /**
     * 构造出[begin,end) 范围的轴点元素
     * @return 轴点元素的最终位置
     */
    private int pivotIndex(int begin ,int end){
        //随机选择一个元素和 begin 位置进行交换（随机确定一个轴点元素）
        //[0,1)  Math.random() * (end - begin)
        swap(begin,begin + (int)(Math.random() * (end - begin)));

        //备份 begin 位置的元素(也是初始的轴点元素)
        E pivot = array[begin];

        //end 指向最后一个元素
        end--;

        //begin和end指针重叠时，此时都指向轴点,所以begin = end作为结束条件
        while (begin < end) {
            //这里来一个循环，当发生交换位置时打破循环，反向
            while (begin < end){
                //从右往左扫描
                //拿出轴点元素和 array[end] 的元素进行比较
                if (cmp(pivot, array[end]) < 0) {
                    //如果end的数要大一些，即右边的元素大于轴点元素
                    //移动 end 指针即可
                    end--;
                }else{
                    //若右边的元素不大于轴点元素 右边元素 <= 轴点元素
                    //交换
                    array[begin++] = array[end];
                    break;
                }
            }

            //这里来一个循环，当发生交换位置时打破循环，反向
            while (begin < end){
                //从左往右扫描
                //拿出轴点元素和 array[begin] 的元素进行比较
                if (cmp(pivot,array[begin])> 0){
                    //如果begin的数要小一些，即左边的元素小于轴点元素
                    //移动 begin 指针即可
                    begin++;
                } else{
                    //若左边的元素不小于轴点元素 左边元素 >= 轴点元素
                    //交换位置
                    array[end--] = array [begin];
                    break;
                }
            }
        }

        //将轴点元素放入最终的位置
        array[begin] = pivot;

        //返回轴点元素的位置
        return begin;
    }
}
